/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/sort-list
   @Language: C++
   @Datetime: 17-01-09 15:40
   */

/**
 * Definition of ListNode
 * class ListNode {
 * public:
 *     int val;
 *     ListNode *next;
 *     ListNode(int val) {
 *         this->val = val;
 *         this->next = NULL;
 *     }
 * }
 */

// Method 1, Merge Sort, Time 48ms
class Solution {
	// merge single list without head node (ascending order)
	ListNode *mergeTwoLists(ListNode *i, ListNode *j){
		ListNode H, *p;
		for (p=&H; i && j; p=p->next){
			if (i->val < j->val){
				p->next = i;
				i = i->next;
			}
			else{
				p->next = j;
				j = j->next;
			}
		}
		p->next = (i ? i:j);
		return H.next;
	}
	ListNode *mergeSortList(ListNode *head) {
		if (head==NULL || head->next==NULL) return head;
		ListNode *fast, *mid, H(-1);
		// find mid node between head and end
		for (H.next=head, fast=mid=&H; fast && fast->next;){
			mid = mid->next;
			fast = fast->next->next;
		}
		fast = mid->next;
		mid->next = NULL;	// cut down mid part from head list
		mid = fast;

		return mergeTwoLists(mergeSortList(head),mergeSortList(mid));
	}

public:
	/**
	 * @param head: The first node of linked list.
	 * @return: You should return the head of the sorted linked list,
	 *          using constant space complexity.
	 * Tips : using merge sort for list sort, ascending order
	 * find the middle node in list, then sort the two part lists
	 * and merge the two sorted lists
	 * using two point fast and mid, which fast move two steps and mid move one
	 **/
	ListNode *sortList(ListNode *head) {
		return mergeSortList(head);
	}
};

// Method 2, Quick Sort, swap ListNode data value, TLE
class Solution {
	void quickSortList(ListNode *begin, ListNode *end){
		if (begin==end || begin==NULL) return;
		ListNode *p, *mid;
		for(mid=begin, p=mid->next; p!=end; p=p->next){
			if (p->val > begin->val) continue;
			mid = mid->next;
			if (mid!=p) swap(p->val,mid->val);
		}
		swap(begin->val,mid->val);
		quickSortList(begin,mid);
		quickSortList(mid->next,end);
	}

public:
	/**
	 * @param head: The first node of linked list.
	 * @return: You should return the head of the sorted linked list,
	 *          using constant space complexity.
	 **/
	ListNode *sortList(ListNode *head) {
		quickSortList(head,NULL);
		return head;
	}
};

// Method 3, Quick Sort, Only change next points, TLE
class Solution {
	void qsort(ListNode *begin, ListNode *end){
		if (begin==NULL || begin->next==end) return;
		ListNode L(-1), R(-1), *key=begin->next;
		ListNode *l=&L, *r=&R, *p;
		for(p=key->next; p!=end; p=p->next)
			if (p->val < key->val) l=l->next=p;
			else r=r->next=p;
		r->next = end;
		if (L.next) begin->next=L.next;
		l->next = key;
		key->next = R.next;
		qsort(begin,key);
		qsort(key,end);
	}
	
public:
	/**
	 * @param head: The first node of linked list.
	 * @return: You should return the head of the sorted linked list,
	 using constant space complexity.
	 */
	ListNode *sortList(ListNode *head) {
		// write your code here
		ListNode H{-1,head};
		qsort(&H,NULL);
		return H.next;
	}
};
